Scheduling a stream of jobs whose holding costs change over time is a classic and practical problem. The seminal work of Van Mieghem (1995) introduced the generalized c-\mu rule for this setting. In this talk, we return to the original problem in a k-class M/M/1 system. We study index policies, which assign each class a priority index based on its current state and serve the class with the highest index.
Finding a good index policy is challenging because it requires reducing this high-dimensional decision problem to a single priority index for each state. Our key idea is to introduce a family of parametric MDPs and use their optimal solutions to derive a recursive characterization of the scheduling index. We use this characterization to identify an optimal index policy for the 2-class M/M/1 problem.